`
https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/
`

/**
 * @param {number} k
 * @return {number}
 */
var preimageSizeFZF = function (k) {
  // 左边界和右边界之差 + 1 就是答案
  return right_bound(k) - left_bound(k) + 1
};

// 搜索 trailingZeroes(n) === K 的左侧边界
function left_bound(target) {
  // 由于 trailingZeroes(n) 大致以 n/4 的速度增长（实际上更接近 n/5 + n/25 + n/125 + ...）
  // 可以将初始 hi 设置为 5 * (k + 1)，这是一个比较安全的估计
  let lo = 0; hi = 5 * (target + 1)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2)
    if (trailingZeroes(mid) < target) {
      lo = mid + 1
    } else {
      hi = mid
    }
  }
  return lo
}

// 搜索 trailingZeroes(n) === K 的右侧边界
function right_bound(target) {
  let lo = 0; hi = 5 * (target + 1)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2)
    if (trailingZeroes(mid) > target) {
      hi = mid
    } else {
      lo = mid + 1
    }
  }
  return lo - 1
}

// https://leetcode.cn/problems/factorial-trailing-zeroes/
var trailingZeroes = function (n) {
  let res = 0;
  let divisor = 5;
  while (divisor <= n) {
    res += Math.floor(n / divisor);
    divisor *= 5;
  }
  return res;
};